Assignment Week 7

MNF130 - Diskrete strukturar (Gruppe 3 og 9)

Assignment - Week 7

👤 Odin Hoff Gardå
✉️ odin.garda@uib.no


❗️Please try to solve the exercises yourself before looking at the solutions.❗️

Injective and surjective functions

4e24b86829adaa0f7634b345282d07f4.png

Let f\colon X\to Yf ⁣:XYf\colon X\to Y be a function. Then fff is

  • injective (or one-to-one) if no two elements in XXX map to the same element under fff. Or in other words, if x\neq yxyx\neq y then f(x)\neq f(y)f(x)f(y)f(x)\neq f(y).
  • surjective (or onto) if all elements in YYY are hit by fff. That is, for all y\in YyYy\in Y there exists some x\in XxXx\in X such that f(x)=yf(x)=yf(x)=y.
  • bijective if fff is both injective and surjective.

Some set operations visualized with Venn diagrams

781b850ffef74c68cefb54a688e078c4.png

f8e9a78856ce4870d2e990ca1cfa5024.png

1d077c8720bb7ee5061dbb05326ea428.png

5aba4a4b5fc3122fbde909178f2919f5.png

Section 2.1 (Edition 8, pg 131-133) 2, 7, 8, 32, 49

Section 2.1 (Global edition, 7, pg 127-128) 2, 4, 5, 21, 28


cd0223f3ff8e13d3c6242ed4730b3cc0.png

There are many ways to do this. Don't worry if your solution is different from the proposed one.

General tips:
- Do you see a pattern or some property all elements in the set share?
- Can you describe this property using symbols?

For example, the set S=\{1,4,9,16,25,36\}S={1,4,9,16,25,36}S=\{1,4,9,16,25,36\} consists of the squares 1^2, 2^2, 3^2, 4^2, 5^2, 6^212,22,32,42,52,621^2, 2^2, 3^2, 4^2, 5^2, 6^2 so we can write SSS as follows using set builder notation:

S=\{n^2\mid n\in\mathbb{Z} \wedge (1\leq n\leq 6)\}
S={n2nZ(1n6)}S=\{n^2\mid n\in\mathbb{Z} \wedge (1\leq n\leq 6)\}
Symbol Meaning
\{{\{ Start of the definition of a set
n^2n2n^2 consider the elements n^2n2n^2
\mid\mid where
n\in\mathbb{Z}nZn\in\mathbb{Z} nnn is an integer
\wedge\wedge and
1\leq n\leq 61n61\leq n\leq 6 nnn is 1,2,3,4,51,2,3,4,51,2,3,4,5 or 666
\}}\} end of the definition of a set

a) Here are three possible ways to do it:

  • \{3n\mid n\in\mathbb{Z}\wedge 0\leq n\leq4\}{3nnZ0n4}\{3n\mid n\in\mathbb{Z}\wedge 0\leq n\leq4\}
  • \{n\in\mathbb{Z}\mid n=3k\text{ for } k\in\{0,1,2,3,4\}\}{nZn=3k for k{0,1,2,3,4}}\{n\in\mathbb{Z}\mid n=3k\text{ for } k\in\{0,1,2,3,4\}\}.
  • \{n\in\mathbb{Z}\mid n\text{ is non-negative, smaller than }13\text{ and is divisible by }3\}{nZn is non-negative, smaller than 13 and is divisible by 3}\{n\in\mathbb{Z}\mid n\text{ is non-negative, smaller than }13\text{ and is divisible by }3\}.

b) \{n\in\mathbb{Z}\mid -3\leq n\leq 3\}{nZ3n3}\{n\in\mathbb{Z}\mid -3\leq n\leq 3\}

c) There is no clearly obvious way to do this. But let's try something:

  • Let AAA denote the set of lower-case letters in the latin alphabet. That is, A=\{a,b,c,d,e,\ldots,w,x,y,z\}A={a,b,c,d,e,,w,x,y,z}A=\{a,b,c,d,e,\ldots,w,x,y,z\}.
  • Now, let's introduce an ordering on the elements in AAA as follows: for \alpha,\beta\in Aα,βA\alpha,\beta\in A define the ordering <<< by letting \alpha<\betaα<β\alpha<\beta if and only if \alphaα\alpha comes before \betaβ\beta in the alphabet. (Remember, a set has no ordering of it elements. But, we are imposing one on AAA now.)
  • For example, if \alpha=cα=c\alpha=c and \beta=aβ=a\beta=a, then \beta<\alphaβ<α\beta<\alpha since aaa comes before bbb in the alphabet.
  • Using our ordered set of letters, we can use set builder notation to complete the task \{m,n,o,p\} = \{\alpha\in A\mid l<\alpha<q\}{m,n,o,p}={αAl<α<q}\{m,n,o,p\} = \{\alpha\in A\mid l<\alpha<q\}.

d98179b0a20bb713b269f67222dbb705.png

Rememeber that every element in a set is unique. So for example, \{a,a,b,c\} = \{a,b,c\}{a,a,b,c}={a,b,c}\{a,a,b,c\} = \{a,b,c\}. Sets cannot encode duplicates! (If you want to do this, you can look up the notion of multisets. But this is probably not a part of this course.)

Also, sets don't care about the order of elements. For example, \{a,b,c\} = \{b,a,c\}{a,b,c}={b,a,c}\{a,b,c\} = \{b,a,c\}.

Note that the set containing aaa is not the same as aaa. That is, \{a\}\neq a{a}a\{a\}\neq a.

a) Yes they are the same set.
b) They are not equal.
c) They are not equal. The set \emptyset\emptyset contains no elements. However, the set \{\emptyset\}{}\{\emptyset\} contains the element \emptyset\emptyset.


8e8352c4cd16ddc58aee9887138f8ecf.png

For a set AAA to be a subset of another set BBB (written A\subseteq BABA\subseteq B, or A\subset BABA\subset B) it is sufficient and necessary that for all elements aaa in AAA, aaa is also in BBB. Symbolically, that is A\subseteq B \iff \forall a (a\in A\implies a\in B)AB    a(aA    aB)A\subseteq B \iff \forall a (a\in A\implies a\in B).

If the set AAA has strictly more elements than BBB, then there is no way AAA can be a subset of (or equal to) BBB. This restricts the number of inclusions you have to check.

For every set AAA, we have A\subseteq AAAA\subseteq A but this is not interesting.

We only have to check the following inclusions:

  1. B\subseteq ABAB\subseteq A True
  2. C\subseteq ACAC\subseteq A True
  3. D\subseteq ADAD\subseteq A False, 8\in D8D8\in D but 8\notin A8A8\notin A
  4. A\subseteq DADA\subseteq D False
  5. B\subseteq DBDB\subseteq D False
  6. C\subseteq DCDC\subseteq D True
  7. B\subseteq CBCB\subseteq C False
  8. C\subseteq BCBC\subseteq B False

acd22643358750f22780798edeea2ede.png

Step 0: Try some examples:

AAA BBB A\times BA×BA\times B
\emptyset\emptyset \emptyset\emptyset \emptyset\emptyset
\{a\}{a}\{a\} \emptyset\emptyset \emptyset\emptyset
\emptyset\emptyset \{b\}{b}\{b\} \emptyset\emptyset
\{a\}{a}\{a\} \{b\}{b}\{b\} \{(a,b)\}{(a,b)}\{(a,b)\}
\{a,c\}{a,c}\{a,c\} \{b\}{b}\{b\} \{(a,b), (c,b)\}{(a,b),(c,b)}\{(a,b), (c,b)\}
\{a,c\}{a,c}\{a,c\} \{b,d\}{b,d}\{b,d\} \{(a,b), (c,b), (a,d), (c,d)\}{(a,b),(c,b),(a,d),(c,d)}\{(a,b), (c,b), (a,d), (c,d)\}
\mathbb{R}R\mathbb{R} \mathbb{R}R\mathbb{R} \mathbb{R}^2R2\mathbb{R}^2

Step 1: Guess some hypothesis!

  • If A\times B=\emptysetA×B=A\times B=\emptyset, what can we say about AAA and BBB?
  • For (most types of) numbers aaa and bbb, recall that ab=0ab=0ab=0 implies that a=0a=0a=0 or b=0b=0b=0. This exercise is somehow the analogue where we have replaced numbers with sets.

Step 2: Prove your hypothesis!

  • Try using the definition of the cartesian product A\times B=\{(a,b)\mid a\in A\wedge b\in B\}A×B={(a,b)aAbB}A\times B=\{(a,b)\mid a\in A\wedge b\in B\} and give a direct proof.
  • OR
  • Think about what you can say about A\times BA×BA\times B if AAA and BBB both contain at least one element.
\begin{align*}
& A\times B =\{(a,b)\mid a\in A\wedge b\in B\} = \emptyset\\
&\iff \neg(\exists a\exists b (a\in A \wedge b\in B))\equiv \forall a\forall b (a\notin A \vee b\notin B)\\
&\iff A=\emptyset \vee B=\emptyset
\end{align*}
A×B={(a,b)aAbB}=    ¬(ab(aAbB))ab(aAbB)    A=B=\begin{align*} & A\times B =\{(a,b)\mid a\in A\wedge b\in B\} = \emptyset\\ &\iff \neg(\exists a\exists b (a\in A \wedge b\in B))\equiv \forall a\forall b (a\notin A \vee b\notin B)\\ &\iff A=\emptyset \vee B=\emptyset \end{align*}

f7145dffe4c5301568e52881452b3e93.png

By the definition of ordered pairs given in the exercise, we have (a,b)=\{\{a\},\{a,b\}\}(a,b)={{a},{a,b}}(a,b)=\{\{a\},\{a,b\}\} and (c,d)=\{\{c\},\{c,d\}\}(c,d)={{c},{c,d}}(c,d)=\{\{c\},\{c,d\}\}. Let us write A=(a,b)A=(a,b)A=(a,b) and C=(c,d)C=(c,d)C=(c,d) to keep things simple. We need to show that A=C\iff (a=c\wedge b=d)A=C    (a=cb=d)A=C\iff (a=c\wedge b=d). We can split the proof into two parts. Namely,

  1. A=C\implies (a=c\wedge b=d)A=C    (a=cb=d)A=C\implies (a=c\wedge b=d) and
  2. (a=c\wedge b=d)\implies A=C(a=cb=d)    A=C(a=c\wedge b=d)\implies A=C.

The implication (2) is easy: if a=ca=ca=c and b=db=db=d, then A=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=CA={{a},{a,b}}={{c},{c,d}}=CA=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=C so we are done.

Now, try to give a convincing argument for (1). That is, argue why \{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}{{a},{a,b}}={{c},{c,d}}\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\} implies that a=ca=ca=c and b=db=db=d. What does it mean for sets to be equal? And how can we check it?

Try to consider the two possible cases a=ba=ba=b and a\neq baba\neq b. If a=ba=ba=b then \{\{a\},\{a,b\}\} = \{\{a\},\{a,a\}\} = \{\{a\},\{a\}\} = \{\{a\}\}{{a},{a,b}}={{a},{a,a}}={{a},{a}}={{a}}\{\{a\},\{a,b\}\} = \{\{a\},\{a,a\}\} = \{\{a\},\{a\}\} = \{\{a\}\}.


Section 2.2 (Edition 8, pg 144-145) 3, 21, 56

Section 2.2 (Global edition, 7, pg 138-140) 2, 11, 30


d0dd9a8da41690bbcfa050e56f4b30e0.png

a) A\cup BABA\cup B consists of all elements that are contained in AAA or BBB (or both).
b) A\cap BABA\cap B consists of all elements that are both in AAA and BBB.
c) and d) A\setminus B = A-BAB=ABA\setminus B = A-B contains all elements of AAA that are not contained in BBB.

a) \{0,1,2,3,4,5,6\}{0,1,2,3,4,5,6}\{0,1,2,3,4,5,6\}
b) \{3\}{3}\{3\}
c) \{1,2,4,5\}{1,2,4,5}\{1,2,4,5\}
d) Similar to (c).


c96fafa8e266d550f6b6f9fcf99ba0e8.png

One way of proving this is to write both sides of the equality symbol using set builder notation and then (hopefully) realize that the two sides represents the same thing.

Recall the following definitions:

  • A-B = \{x\mid x\in A\wedge x\notin B\}AB={xxAxB}A-B = \{x\mid x\in A\wedge x\notin B\}
  • \bar{A} = \{x\mid x\notin A\}Aˉ={xxA}\bar{A} = \{x\mid x\notin A\}
  • A\cap B = \{x\mid x\in A\wedge x\in B\}AB={xxAxB}A\cap B = \{x\mid x\in A\wedge x\in B\}
  • A\cup B = \{x\mid x\in A\vee x\in B\}AB={xxAxB}A\cup B = \{x\mid x\in A\vee x\in B\}

Another way is to show that the left-hand side is contained in the right-hand side, and the other way around.

You could also try to use a Venn diagram, or use some set identities you know.

b) (A\cap B)\cup(A\cap\bar{B}) = \{x\mid (x\in A\wedge x\in B)\vee (x\in A \wedge x\notin B) \} = \{x\mid (x\in A)\wedge(x\in B \vee x\notin B) \} = \{x\mid (x\in A)\wedge\textbf{T} \}=\{x\mid x\in A\} = A(AB)(ABˉ)={x(xAxB)(xAxB)}={x(xA)(xBxB)}={x(xA)T}={xxA}=A(A\cap B)\cup(A\cap\bar{B}) = \{x\mid (x\in A\wedge x\in B)\vee (x\in A \wedge x\notin B) \} = \{x\mid (x\in A)\wedge(x\in B \vee x\notin B) \} = \{x\mid (x\in A)\wedge\textbf{T} \}=\{x\mid x\in A\} = A


469471ab6b3dd66bf7abd35fbc464ff9.png

  1. Write it out. For example, if A_i=(0,i)Ai=(0,i)A_i=(0,i), then we can write \bigcup_{i=1}^\infty A_i = \bigcup_{i=1}^\infty(0,i) = (0,1)\cup(0,2)\cup(0,3)\cup\ldots\cup(0,i)\cup\ldotsi=1Ai=i=1(0,i)=(0,1)(0,2)(0,3)(0,i)\bigcup_{i=1}^\infty A_i = \bigcup_{i=1}^\infty(0,i) = (0,1)\cup(0,2)\cup(0,3)\cup\ldots\cup(0,i)\cup\ldots.
  2. Remember: an element xxx is in \bigcup_{i=1}^\infty A_ii=1Ai\bigcup_{i=1}^\infty A_i if and only if xxx is contained in at least one of the A_iAiA_i's for some value of iii.
  3. Remember: an element xxx is in \bigcap_{i=1}^\infty A_ii=1Ai\bigcap_{i=1}^\infty A_i if and only if xxx is contained in A_iAiA_i for ALL values of i=1,2,3,4,\ldotsi=1,2,3,4,i=1,2,3,4,\ldots
  4. Maybe it can be helpful to visualize/draw it?

a)

\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty\{i,i+1,i+2,\ldots,\} = \{1,2,3,4,\ldots\}\cup\{2,3,4,5\ldots\}\cup\ldots = \{1,2,3,4,5,6,\ldots\} = \{n\in\mathbb{Z}\mid n>0\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty\{i,i+1,i+2,\ldots,\} = \{1,2,3,4,\ldots\}\cap\{2,3,4,5\ldots\}\cap\ldots = \emptyset
\end{align*}
i=1Ai=i=1{i,i+1,i+2,,}={1,2,3,4,}{2,3,4,5}={1,2,3,4,5,6,}={nZn>0}i=1Ai=i=1{i,i+1,i+2,,}={1,2,3,4,}{2,3,4,5}=\begin{align*} \bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty\{i,i+1,i+2,\ldots,\} = \{1,2,3,4,\ldots\}\cup\{2,3,4,5\ldots\}\cup\ldots = \{1,2,3,4,5,6,\ldots\} = \{n\in\mathbb{Z}\mid n>0\}\\ \bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty\{i,i+1,i+2,\ldots,\} = \{1,2,3,4,\ldots\}\cap\{2,3,4,5\ldots\}\cap\ldots = \emptyset \end{align*}

The last one (intersection): if n\in\bigcap_{i=1}^\infty A_ini=1Ain\in\bigcap_{i=1}^\infty A_i then n\in A_inAin\in A_i for all choices of iii. Choose i=n+1i=n+1i=n+1, then n\in A_{n+1} = \{n+1, n+2, n+3,\ldots\}nAn+1={n+1,n+2,n+3,}n\in A_{n+1} = \{n+1, n+2, n+3,\ldots\} which is clearly not true. Hence, there are exists not nnn such that n\in\bigcap_{i=1}^\infty A_ini=1Ain\in\bigcap_{i=1}^\infty A_i which means it is the empty set.

b)

\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty\{0,i\} = \{0,1\}\cup\{0,2\}\cup\{0,3\}\cup\ldots = \{0,1,2,3,4,\ldots\}= \{n\in\mathbb{Z}\mid n\geq 0\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty\{0,i\} = \{0,1\}\cap\{0,2\}\cap\{0,3\}\cap\ldots = \{0\}
\end{align*}
i=1Ai=i=1{0,i}={0,1}{0,2}{0,3}={0,1,2,3,4,}={nZn0}i=1Ai=i=1{0,i}={0,1}{0,2}{0,3}={0}\begin{align*} \bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty\{0,i\} = \{0,1\}\cup\{0,2\}\cup\{0,3\}\cup\ldots = \{0,1,2,3,4,\ldots\}= \{n\in\mathbb{Z}\mid n\geq 0\}\\ \bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty\{0,i\} = \{0,1\}\cap\{0,2\}\cap\{0,3\}\cap\ldots = \{0\} \end{align*}

c)

\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty(0,i) = (0,1)\cup(0,2)\cup(0,3)\cup\ldots\cup(0,i)\cup\ldots = (0,\infty) = \{x\in \mathbb{R}\mid x>0\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty(0,i) = (0,1)\cap(0,2)\cap(0,3)\cap\ldots\cap(0,i)\cap\ldots = (0,1)
\end{align*}
i=1Ai=i=1(0,i)=(0,1)(0,2)(0,3)(0,i)=(0,)={xRx>0}i=1Ai=i=1(0,i)=(0,1)(0,2)(0,3)(0,i)=(0,1)\begin{align*} \bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty(0,i) = (0,1)\cup(0,2)\cup(0,3)\cup\ldots\cup(0,i)\cup\ldots = (0,\infty) = \{x\in \mathbb{R}\mid x>0\}\\ \bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty(0,i) = (0,1)\cap(0,2)\cap(0,3)\cap\ldots\cap(0,i)\cap\ldots = (0,1) \end{align*}

d)

\begin{align*}
\bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty(i,\infty) = (1,\infty)\cup(2,\infty)\cup(3,\infty)\cup\ldots = (1,\infty) = \{x\in \mathbb{R}\mid x>1\}\\
\bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty(i,\infty) = (1,\infty)\cap(2,\infty)\cap(3,\infty)\cap\ldots = \emptyset
\end{align*}
i=1Ai=i=1(i,)=(1,)(2,)(3,)=(1,)={xRx>1}i=1Ai=i=1(i,)=(1,)(2,)(3,)=\begin{align*} \bigcup_{i=1}^\infty A_i &= \bigcup_{i=1}^\infty(i,\infty) = (1,\infty)\cup(2,\infty)\cup(3,\infty)\cup\ldots = (1,\infty) = \{x\in \mathbb{R}\mid x>1\}\\ \bigcap_{i=1}^\infty A_i &= \bigcap_{i=1}^\infty(i,\infty) = (1,\infty)\cap(2,\infty)\cap(3,\infty)\cap\ldots = \emptyset \end{align*}

Explanation for the last one: Assume xxx is an element of \bigcap_{i=1}^\infty(i,\infty)i=1(i,)\bigcap_{i=1}^\infty(i,\infty). Then, x\in(i,\infty)x(i,)x\in(i,\infty) for all values of iii by the definition of the intersection. But choose iii to be some integer larger than xxx (for example, choose i=\lceil x \rceil+1i=x+1i=\lceil x \rceil+1) and we have x\notin (i,\infty)x(i,)x\notin (i,\infty) which is a contradiction. Therefore, our assumption must be wrong. That is, there are no elements in \bigcap_{i=1}^\infty(i,\infty)i=1(i,)\bigcap_{i=1}^\infty(i,\infty) which means that it must be the empty set \emptyset\emptyset.


Section 2.3 (Edition 8, pg 161-164) 2, 10, 23, 41

Section 2.3 (Global edition, 7, pg 153-155) 2, 6, 15, 25


21a47ff5ffd9967d554da84e7731df00.png

a) What is the definition of a function? Can a function map an element to two elements?
b) Does it satisfy what it takes to be a function \mathbb{Z}\to\mathbb{R}ZR\mathbb{Z}\to\mathbb{R}?
c) Is it defined for all values in the domain \mathbb{Z}Z\mathbb{Z}?

a) No, a function f\colon A\to Bf ⁣:ABf\colon A\to B maps an element a\in AaAa\in A to exaclty one element f(a)\in Bf(a)Bf(a)\in B.
b) Yes this defines a function f\colon\mathbb{Z}\to\mathbb{R}f ⁣:ZRf\colon\mathbb{Z}\to\mathbb{R}.
c) No, the expression is undefined whenever n=2n=2n=2 or n=-2n=2n=-2.


10327aaedfb00562a950e4046f7e4efc.png

What is the definition of being one-to-one (injective)?
How can a function fail to be one-to-one?
Can a function that maps two or more elements to the same element be injective?


ba70a12738d4613846db518637b8dd05.png

A bijection is a function that is both injective (one-to-one) and surjective (onto).

a) Yes (Check it!)
b) No (Same reason as (d). See below.)
c) Yes (Check it!)
d) No (It's always positive so it can't be surjective. Also, f(x)=f(-x)f(x)=f(x)f(x)=f(-x) so it's not injective either.)


b1c1f164b964b9b77e108d0e69e1bba6.png

Set y=ax+by=ax+by=ax+b and solve for xxx. How does this give you the inverse of fff?

Here is a graphical "proof" that a linear function (in one dimension) is invertible:

b23ab6b693ad746c89c78a42900bc870.png

Writing y=ax+by=ax+by=ax+b and solving for xxx we get x=\frac{y-b}{a}x=ybax=\frac{y-b}{a}. So I claim that g(y) = \frac{y-b}{a}g(y)=ybag(y) = \frac{y-b}{a} is the inverse of fff.

Let's check the claim:

  1. f(g(y)) = f(\frac{y-b}{a}) = a\frac{y-b}{a}+b = y-b+b = yf(g(y))=f(yba)=ayba+b=yb+b=yf(g(y)) = f(\frac{y-b}{a}) = a\frac{y-b}{a}+b = y-b+b = y and
  2. g(f(x)) = g(ax+b) = \frac{ax+b-b}{a} = \frac{ax}{a} = xg(f(x))=g(ax+b)=ax+bba=axa=xg(f(x)) = g(ax+b) = \frac{ax+b-b}{a} = \frac{ax}{a} = x.

Indeed we have that g=f^{-1}g=f1g=f^{-1}.


Additional exercises

f4beca8f3e534ad6b9cf4837378f696d.png

0b64c847f411e27c7caa41957acd7783.png

2e443295b15e2b20232772e0e349d5c4.png


30832c7d164cbaa38ea8d3a99e3726bd.png

dd304c3d57af7f23dcfc9ed06842a2e7.png

7d06139eee8fa7991765868121910ea3.png